public class test06 {
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            //正：x
            //负：tar-x
            //sum = 2x-tar
            //所以x = （sum+tar）/2
            int sum = 0;
            for(int num:nums){
                sum += num;
            }
            if(sum<Math.abs(target)){
                return 0;
            }
            if((sum+target)%2!=0){
                return 0;
            }
            int[] dp = new int[(sum+target)/2+1];
            //初始化
            dp[0] = 1;
            for(int i = 0;i<nums.length;i++){
                for(int j = (sum+target)/2;j>=nums[i];j--){
                    dp[j] += dp[j-nums[i]];
                }
            }
            return dp[(sum+target)/2];
        }
    }
}
